package middle;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import util.PrintUtils;

public class Solution_210 {

    public static void main(String[] args) {
        Solution_210 model = new Solution_210();
        PrintUtils.arrayInt(model.findOrder(2, new int[][]{{1, 0}}));
        PrintUtils.arrayInt(model.findOrder(4, new int[][]{{1,0},{2,0},{3,1},{3,2}}));
        PrintUtils.arrayInt(model.findOrder(1, new int[][]{}));
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] counts = new int[numCourses];
        Set<Integer>[] sets = new Set[numCourses];
        for (int[] prerequisite : prerequisites) {
            counts[prerequisite[0]]++;
            Set<Integer> set = sets[prerequisite[1]];
            if (set == null) {
                set = new HashSet<>();
            }
            sets[prerequisite[1]] = set;
            set.add(prerequisite[0]);
        }

        List<Integer> list = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            Integer parent = queue.poll();
            list.add(parent);
            Set<Integer> set = sets[parent];
            if (set != null) {
                for (Integer child : set) {
                    counts[child]--;
                    if (counts[child] == 0) {
                        queue.add(child);
                    }
                }
            }
        }
        if (list.size() != numCourses) {
            return new int[0];
        }
        int[] rst = new int[numCourses];
        for (int i = 0; i < list.size(); i++) {
            rst[i] = list.get(i);
        }
        return rst;
    }
}
